package main

import (
	"fmt"
	"sort"
)

var result [][]int
var arr []int

func permuteUnique(nums []int) [][]int {
	result = nil
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})
	visited := make([]bool, len(nums))
	doPermute(nums, visited)
	return result
}

func doPermute(nums []int, visited []bool) {
	if len(arr) == len(nums) {
		item := make([]int, len(arr))
		copy(item, arr)
		result = append(result, item)
	} else {
		for i := 0; i < len(nums); i++ {
			if visited[i] {
				continue
			}
			if i > 0 && !visited[i-1] && nums[i-1] == nums[i] {
				continue
			}
			visited[i] = true
			arr = append(arr, nums[i])
			doPermute(nums, visited)
			// back
			arr = arr[0 : len(arr)-1]
			visited[i] = false
		}
	}
}

func main() {
	r := permuteUnique([]int{1, 2, 2})
	fmt.Printf("%v", r)
}
